Digital information processors frequently employ digital memory buffers to temporarily store information en route to another device such as an input/output device or processor. A buffer may be constructed of dedicated hardware registers wired together or it may simply be a dedicated section of a larger memory. Such digital information buffers can take many forms. One such form is known as a circular buffer. In circular buffers, the addresses for accessing locations in the buffers typically are generated by modifying the contents of a pointer register which is external to the buffer area which points to an address location within the buffer. When that address is needed on the address bus, it is output from the pointer address and the pointer is incremented (or decremented) by a predetermined amount so as to be ready for the next instruction cycle which accesses the circular buffer. In circular buffers, means must be provided for “wrapping” the address around when the increment (or decrement) causes the address in the pointer register to fall without the bounds of the buffer. In other words, means must be provided for causing the address generator for the buffer to generate modulo addresses with the modulus being the length of the buffer.
In circular buffers, software techniques are generally used for the modulo address generation. These software address mapping techniques, however, require several instruction cycles to perform the necessary address comparisons, arithmetic operations and replacement of the pointer register contents. Such software address mapping is not fast enough for certain types of uses. Applications such as digital filters, Fast Fourier transforms, matrix manipulations and other common digital signal processing routines require a very rapid generation of memory references. Accordingly, software modulo address generation can significantly decrease the speed of fast signal processing apparatus. Accordingly, addressing schemes implemented in hardware are sometimes desirable.
One such hardware implemented system is disclosed in U.S. Pat. No. 4,800,524. The apparatus described in U.S. Pat. No. 4,800,524 comprises three registers external to the buffer, including (1) an L register which contains the length of the buffer, (2) an A register which contains the last address accessed in the buffer (this is the pointer register) and (3) an M buffer which contains an increment (or decrement) value to be added (or subtracted) from the A register. The apparatus also comprises two separate adder/subtractors, the first of which generates an absolute buffer address which is simply the contents of the A register added to the contents of the M register and a second adder/subtractor which generates a wrapped address by either adding (if M is positive) or subtracting (if M is negative) from the absolute address generated by the first adder the length of the buffer. Additional logic selects either the absolute address or the wrapped address responsive to the carry bits from the first and second adders. If the carry bits indicate that the absolute address generated is outside the boundaries of the buffer, the wrapped address is used and placed in the A register ready for the next access. Otherwise, the absolute address is selected and placed in the A register. The invention disclosed in the U.S. Pat. No. 4,800,524 patent is limited, however, in that in order for the system of examining the carry bits to work, the lower K bits of the buffer's base address (lowest address) must be zero, where K is the number of bits required to represent the length of the buffer and the length of the buffer must be a power of two. These limitations can be extremely inconvenient in certain applications.
It is one object of the present invention to provide an improved address generator for a circular buffer.
It is a further object of the present invention to provide an address generator for a circular buffer which places no restrictions on the size or the position in memory of the circular buffer.
It is another object of the present invention is to provide an address generator for a circular buffer which is substantially faster than software address generators.